/*
 * @lc app=leetcode.cn id=442 lang=cpp
 *
 * [442] 数组中重复的数据
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n  =nums.size();

        vector<int> res;

        int toIndex;

        for (int i=0;i<n;++i){
            bool foundEmptyIndex = false;

            if (i + 1 == nums[i]){
                continue;
            }else{
                toIndex = nums[i];
                nums[i] = -1;
            }

            while (nums[toIndex-1] != toIndex){
                if (nums[toIndex-1] == -1){
                    nums[toIndex-1] = toIndex;
                    foundEmptyIndex = true;
                    break;
                }

                int temp = nums[toIndex-1];
                nums[toIndex-1] = toIndex;
                toIndex = temp;
            }
            
            if (foundEmptyIndex) {continue;}

            res.emplace_back(toIndex);
        }

        return res;
    }
};
// @lc code=end

